Fragmentation of data base indexes can have a significant impact on input/output (I/O) costs associated with responding to database queries. For example, an index can be externally fragmented when the logical order of the index's pages is different than the physical order that the pages are stored on disc. Alternatively or additionally, indexes can be internally fragmented when the storage capacity of individual index pages is not fully utilized. As a result of the index being internally fragmented, more index pages might be used to store data (e.g., records) than would otherwise be necessary if the index were not internally fragmented As a result of the index being externally fragmented, more I/O operations might be performed to respond to a query than would otherwise be performed if the index were not internally fragmented.
Defragmenting indexes, however, can also involve significant I/O costs. As such, database administers typically employ defragmenting operations judiciously. Unfortunately, the number of defragmentation options and tools currently available to database managers are limited. For example, entire indexes typically need to be defragmented, which can be costly. Furthermore, database managers are typically limited to relying on rules of thumb based on index size and fragmentation statistics when trying to determine which index(es) of a database to defragment. This data-driven type of approach, however, can lead to the defragmentation of indexes that have little or no impact on the performance of queries or other search statements on the database.